package edu.rice.test;

import java.util.concurrent.ExecutorCompletionService;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 
 * @author Ian Schneider
 */
public class MTMatrix {
	public static void main(String[] args) {
		System.out.println("warmup");
		doit(100, 100, 2);
		System.out.println("completed");
		System.out.println();
		for (int i = 5; i <= 10; i += 5) {
			doit(i, i, 1);
			doit(i, i, 2);
			doit(i, i, 4);
			System.out.println();
		}
	}

	static int[][] bigEffinMatrix(int r, int c) {
		int[][] m = new int[r][c];
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				m[i][j] = (int) (Math.random() * 10);
			}
		}
		return m;
	}

	static boolean equals(int[][] a, int[][] b) {
		boolean eq = true;
		for (int i = 0; i < a.length && eq; i++) {
			for (int j = 0; j < b[i].length && eq; j++) {
				eq &= a[i][j] == b[i][j];
			}
		}
		return eq;
	}

	static void doit(int r, int c, int t) {
		System.gc();
		System.gc();
		System.runFinalization();
		int[][] a = bigEffinMatrix(r, c);
		int[][] b = bigEffinMatrix(r, c);
		long time = System.currentTimeMillis();
		int[][] m = mult(a, b);
		showMatrix(m);
		System.out.println("single thread : "
				+ (System.currentTimeMillis() - time));
		time = System.currentTimeMillis();
		try {
			int[][] n = mtmult(a, b, t);
			showMatrix(n);
			System.out.println("mt " + t + " "
					+ (System.currentTimeMillis() - time));
			assert equals(m, n) : "answers not equals";
			assert checksum(m,n) : "answer not euqlas";
		} catch (InterruptedException ie) {
			assert false;
		}
		System.gc();
		System.gc();
		System.runFinalization();
		time = System.currentTimeMillis();
		try {
			int[][] n = mtmult2(a, b, t);
			showMatrix(n);
			System.out.println("mt2 " + t + " "
					+ (System.currentTimeMillis() - time));
			assert equals(m, n) : "answers not equals";
			assert checksum(m,n) : "answer not euqlas";
		} catch (InterruptedException ie) {
			assert false;
		}
		System.gc();
		System.gc();
		System.runFinalization();
		time = System.currentTimeMillis();
		try {
			int[][] n = mtmult3(a, b, t);
			showMatrix(n);
			System.out.println("mt3 " + t + " "
					+ (System.currentTimeMillis() - time));
			assert equals(m, n) : "answer not equals";
			assert checksum(m,n) : "answer not euqlas";
		} catch (InterruptedException ie) {
			assert false;
		}

	}

	static void computeRow(int[][] a, int[][] b, int[][] c, int r) {
		final int cols = b[0].length;
		for (int j = 0; j < cols; ++j) {
			for (int k = 0; k < a[r].length; ++k) {
				c[r][j] += a[r][k] * b[k][j];
			}
		}
	}

	public static int[][] mult(int[][] a, int[][] b) {
		int rows = a.length;
		int cols = b[0].length;
		int[][] c = new int[rows][cols];
		for (int i = 0; i < rows; ++i) {
			computeRow(a, b, c, i);
		}
		return c;
	}

	public static int[][] mtmult(final int[][] a, final int[][] b, int t)
			throws InterruptedException {
		final int[][] c = new int[a.length][b[0].length];
		ExecutorService es = Executors.newFixedThreadPool(t);
		ExecutorCompletionService ecs = new ExecutorCompletionService(es);
		for (int i = 0; i < a.length; ++i) {
			final int row = i;
			ecs.submit(new Runnable() {
				public void run() {
					computeRow(a, b, c, row);
				}
			}, null);
		}
		for (int i = 0; i < a.length; ++i) {
			ecs.take();
		}
		es.shutdown();
		return c;
	}

	public static int[][] mtmult2(final int[][] a, final int[][] b, int t)
			throws InterruptedException {
		final int[][] c = new int[a.length][b[0].length];
		final AtomicInteger row = new AtomicInteger();
		final int rows = a.length;
		Thread[] threads = new Thread[t];
		for (int i = 0; i < threads.length; i++) {
			threads[i] = new Thread(new Runnable() {
				public void run() {
					int r;
					while ((r = row.getAndIncrement()) < rows) {
						computeRow(a, b, c, r);
					}
				}
			});
			threads[i].start();
		}
		for (int i = 0; i < threads.length; i++) {
			threads[i].join();
		}
		return c;
	}

	public static int[][] mtmult3(final int[][] a, final int[][] b, int t) throws InterruptedException {
		final int[][] c = new int[a.length][b[0].length];
		Thread[] threads = new Thread[t];
		for (int i = 0; i < threads.length; i++) {
			threads[i] = new Thread(new mtr(i * a.length / threads.length,
					a.length / threads.length, a, b, c));
			threads[i].start();
		}
		for (int i = 0; i < threads.length; i++) {
			threads[i].join();

		}
		return c;
	}

	static class mtr implements Runnable {
		int subs;
		int subn;

		public mtr(int s, int n, int[][] a, int[][] b, int[][] c) {
			subs = s;
			subn = n;
			this.a = a;
			this.b = b;
			this.c = c;
		}

		int[][] a;
		int[][] b;
		int[][] c;

		public void run() {
			for (int i = 0; i < subn; i++) {
				computeRow(a, b, c, i + subs);
			}
		}
	}
	
	public static boolean checksum(int[][] a, int[][] b){
		boolean equals;
		if(a.length != b.length || a[0].length != b[0].length){
			equals = false;
			return equals;
		}
		double eps = 1e-6;
		double sum = 0;
		for(int i = 0; i < a.length; i++){
			for(int j = 0; j < a[0].length; j++){
				sum += Math.abs(a[i][j]-b[i][j]);
			}
		}
		if(sum < eps){
			equals = true;
			return equals;
		}else{
			equals = false;
			return equals;
		}
	}
	
	public static void showMatrix(int[][] a){
		for(int i = 0; i < a.length; i++){
			for(int j = 0; j < a[0].length; j++){
				System.out.print(a[i][j] + "   ");
			}
			System.out.println();
		}
			
	}
}
